//给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [1,3,null,null,2]
//输出：[3,1,null,null,2]
//解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
// 
//
// 示例 2： 
// 
// 
//输入：root = [3,1,4,null,null,2]
//输出：[2,1,4,null,null,3]
//解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。 
//
// 
//
// 提示： 
//
// 
// 树上节点的数目在范围 [2, 1000] 内 
// -2³¹ <= Node.val <= 2³¹ - 1 
// 
//
// 
//
// 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？ 
//
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 863 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void recoverTree(TreeNode root) {
        ArrayList<TreeNode> integers = new ArrayList<>();
         TreeNode a=null;
         TreeNode b=null;
         bianli(root,integers);
        for (int i = 0; i < integers.size()-1; i++) {
            if(integers.get(i).val>integers.get(i+1).val){
                a=integers.get(i);
                break;
            }
        }

        for (int i = integers.size()-1; i >=1 ; i--) {
            if(integers.get(i).val<integers.get(i-1).val){
                b=integers.get(i);
                break;
            }
        }
//        for (int i = integers.size() - 2; i >= 0; i--) { // 修改循环的结束条件为 i >= 0
//            if (integers.get(i).val > integers.get(i + 1).val) { // 修改条件为 > 号
//                b = integers.get(i + 1); // 修改为获取后一个节点
//                break;
//            }
//        }
        int tem=a.val;
        a.val=b.val;
        b.val=tem;
    }
    void bianli(TreeNode root, List list){
        if(root==null){
            return;
        }
        bianli(root.left,list);
        list.add(root);
        bianli(root.right,list);
    }

}
//leetcode submit region end(Prohibit modification and deletion)
